import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 26727
 * Date: 2025-09-06
 * Time: 22:33
 */
public class Test88 {
    public static void main(String[] args) {
        String s = "leetcode";
        List<String> wordDict = Arrays.asList("leet", "code");;
        boolean ret = wordBreak(s,wordDict);
        System.out.println(ret);;
    }

    public static boolean wordBreak(String s, List<String> wordDict) {
        Set<String> hash = new HashSet<>(wordDict);
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        dp[0] = true;
        s = " " + s;
        for(int i = 1; i <= n; i++) {
            for(int j = i; j >= 1; j--) {
                if(dp[j-1] && hash.contains(s.substring(j,i+1))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
}
